package month1;

import java.util.*;

public class Subsets78_06 {
    public static void main(String[] args) {
        System.out.println(subsets(new int[]{1, 2, 3}));
    }

    /**
     * 简单回溯
     * @param nums
     * @return
     */
    static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        traceback(nums, ret, new ArrayList<>(), 0);
        return ret;
    }

    static void traceback(int[] nums, List<List<Integer>> ret, List<Integer> tmp, int j) {
        ret.add(new ArrayList(tmp));
        for (int i = j; i < nums.length; ++i) {
            tmp.add(nums[i]);
            traceback(nums, ret, tmp, i + 1);
            tmp.remove(tmp.size() - 1);
        }
    }
}
